package week3;

import base.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 *
 * 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 *
 *
 * 执行结果： 通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了99.58% 的用户
 * 内存消耗：38.2 MB, 在所有 Java 提交中击败了90.66% 的用户
 *
 *
 */
public class Week3ConstructBinaryTreeFromPreorderAndInorderTraversal {


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode firstNode = new TreeNode(preorder[0]); // 构建 root 节点
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(firstNode);
        int inorderIndex = 0;
        for(int size = 1; size < preorder.length; size++) {
            int preorderValue = preorder[size];
            TreeNode node = stack.peek();
            if(node.val != inorder[inorderIndex]) {
                // 根据 preorder 和 inorder 确定 left 节点
                node.left = new TreeNode(preorderValue);
                stack.push(node.left);
            } else {
                // 确定 right 节点
                for(;!stack.isEmpty() && stack.peek().val == inorder[inorderIndex];) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderValue);
                stack.push(node.right);
            }
        }

        return firstNode;
    }
}
